home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 15 / CU Amiga Magazine's Super CD-ROM 15 (1997)(EMAP Images)(GB)[!][issue 1997-10].iso / CUCD / Graphics / Ghostscript / source / gxcpath.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-05-04  |  30.7 KB  |  1,016 lines
  1. /* Copyright (C) 1991, 1995, 1996, 1997 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of Aladdin Ghostscript.
  4.   
  5.   Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author
  6.   or distributor accepts any responsibility for the consequences of using it,
  7.   or for whether it serves any particular purpose or works at all, unless he
  8.   or she says so in writing.  Refer to the Aladdin Ghostscript Free Public
  9.   License (the "License") for full details.
  10.   
  11.   Every copy of Aladdin Ghostscript must include a copy of the License,
  12.   normally in a plain ASCII text file named PUBLIC.  The License grants you
  13.   the right to copy, modify and redistribute Aladdin Ghostscript, but only
  14.   under certain conditions described in the License.  Among other things, the
  15.   License requires that the copyright notice and this notice be preserved on
  16.   all copies.
  17. */
  18.  
  19. /* gxcpath.c */
  20. /* Implementation of clipping paths */
  21. #include "gx.h"
  22. #include "gserrors.h"
  23. #include "gsstruct.h"
  24. #include "gsutil.h"
  25. #include "gxdevice.h"
  26. #include "gxfixed.h"
  27. #include "gscoord.h"        /* needs gsmatrix.h */
  28. #include "gzpath.h"
  29. #include "gzcpath.h"
  30.  
  31. /* Define whether to look for vertical clipping regions. */
  32. #define CHECK_VERTICAL_CLIPPING
  33.  
  34. /* Imported from gxacpath.c */
  35. extern int gx_cpath_intersect_slow(P4(gs_state *, gx_clip_path *,
  36.   gx_path *, int));
  37.  
  38. /* Forward references */
  39. private void gx_clip_list_from_rectangle(P2(gx_clip_list *, gs_fixed_rect *));
  40. private int gx_clip_list_add_to_path(P2(gx_clip_list *, gx_path *));
  41.  
  42. /* Structure types */
  43. public_st_clip_rect();
  44. private_st_clip_list();
  45. public_st_clip_path();
  46. public_st_device_clip();
  47.  
  48. /* GC procedures for gx_clip_path */
  49. #define cptr ((gx_clip_path *)vptr)
  50. private ENUM_PTRS_BEGIN(clip_path_enum_ptrs) ;
  51.     if ( index < st_clip_list_max_ptrs )
  52.       { gs_ptr_type_t ret = clip_list_enum_ptrs(&cptr->list, sizeof(cptr->list), index, pep);
  53.         if ( ret == 0 )    /* don't stop early */
  54.           ret = ptr_struct_type, *pep = 0;
  55.         return ret;
  56.       }
  57.     return (*st_path.enum_ptrs)(&cptr->path, sizeof(cptr->path), index - st_clip_list_max_ptrs, pep);
  58. ENUM_PTRS_END
  59. private RELOC_PTRS_BEGIN(clip_path_reloc_ptrs) {
  60.     clip_list_reloc_ptrs(&cptr->list, sizeof(gx_clip_list), gcst);
  61.     (*st_path.reloc_ptrs)(&cptr->path, sizeof(gx_path), gcst);
  62. } RELOC_PTRS_END
  63. #undef cptr
  64.  
  65. /* GC procedures for gx_device_clip */
  66. #define cptr ((gx_device_clip *)vptr)
  67. private ENUM_PTRS_BEGIN(device_clip_enum_ptrs) {
  68.     if ( index < st_clip_list_max_ptrs + 1 )
  69.       return clip_list_enum_ptrs(&cptr->list, sizeof(gx_clip_list),
  70.                      index - 1, pep);
  71.     return (*st_device_forward.enum_ptrs)(vptr, sizeof(gx_device_forward),
  72.                           index - (st_clip_list_max_ptrs + 1), pep);
  73.     }
  74.     case 0:
  75.       ENUM_RETURN((cptr->current == &cptr->list.single ? NULL :
  76.                (void *)cptr->current));
  77. ENUM_PTRS_END
  78. private RELOC_PTRS_BEGIN(device_clip_reloc_ptrs) {
  79.     if ( cptr->current == &cptr->list.single )
  80.       cptr->current =
  81.         &((gx_device_clip *)gs_reloc_struct_ptr(vptr, gcst))->list.single;
  82.     else
  83.       RELOC_PTR(gx_device_clip, current);
  84.     clip_list_reloc_ptrs(&cptr->list, sizeof(gx_clip_list), gcst);
  85.     (*st_device_forward.reloc_ptrs)(vptr, sizeof(gx_device_forward), gcst);
  86. } RELOC_PTRS_END
  87. #undef cptr
  88.  
  89. /* Define an empty clip list. */
  90. private const gx_clip_list clip_list_empty =
  91. {  { 0, 0, min_int, max_int, 0, 0 },
  92.    0, 0, 0, 0 /*false*/
  93. };
  94.  
  95. /* Debugging */
  96.  
  97. #ifdef DEBUG
  98. /* Validate a clipping path. */
  99. bool        /* only exported for gxacpath.c */
  100. clip_list_validate(const gx_clip_list *clp)
  101. {    if ( clp->count <= 1 )
  102.       return (clp->head == 0 && clp->tail == 0 &&
  103.           clp->single.next == 0 && clp->single.prev == 0);
  104.     else
  105.       {    const gx_clip_rect *prev = clp->head;
  106.         const gx_clip_rect *ptr;
  107.         bool ok = true;
  108.         while ( (ptr = prev->next) != 0 )
  109.           { if ( ptr->ymin > ptr->ymax || ptr->xmin > ptr->xmax ||
  110.              !(ptr->ymin >= prev->ymax ||
  111.                (ptr->ymin == prev->ymin &&
  112.                 ptr->ymax == prev->ymax &&
  113.                 ptr->xmin >= prev->xmax)) ||
  114.              ptr->prev != prev
  115.                )
  116.               { clip_rect_print('q', "WRONG:", ptr);
  117.             ok = false;
  118.               }
  119.             prev = ptr;
  120.           }
  121.         return ok && prev == clp->tail;
  122.       }
  123. }
  124. #endif
  125.  
  126. /* ------ Clipping path accessing ------ */
  127.  
  128. /* Return the path of a clipping path. */
  129. int
  130. gx_cpath_path(gx_clip_path *pcpath, gx_path *ppath)
  131. {    if ( !pcpath->segments_valid )
  132.     {    int code = gx_clip_list_add_to_path(&pcpath->list, &pcpath->path);
  133.         if ( code < 0 ) return code;
  134.         pcpath->segments_valid = 1;
  135.     }
  136.     *ppath = pcpath->path;
  137.     return 0;
  138. }
  139.  
  140. /* Return the inner and outer check rectangles for a clipping path. */
  141. /* Return true iff the path is a rectangle. */
  142. /* Note that these must return something strange if we are using */
  143. /* outside clipping. */
  144. bool
  145. gx_cpath_inner_box(const gx_clip_path *pcpath, gs_fixed_rect *pbox)
  146. {    if ( pcpath->list.outside )
  147.       { pbox->p.x = pbox->p.y = pbox->q.x = pbox->q.y = 0;
  148.         return false;
  149.       }
  150.     else
  151.       { *pbox = pcpath->inner_box;
  152.         return clip_list_is_rectangle(&pcpath->list);
  153.       }
  154. }
  155. bool
  156. gx_cpath_outer_box(const gx_clip_path *pcpath, gs_fixed_rect *pbox)
  157. {    if ( pcpath->list.outside )
  158.       { pbox->p.x = pbox->p.y = min_fixed;
  159.         pbox->q.x = pbox->q.y = max_fixed;
  160.         return false;
  161.       }
  162.     else
  163.       { *pbox = pcpath->outer_box;
  164.         return clip_list_is_rectangle(&pcpath->list);
  165.       }
  166. }
  167.  
  168. /* Test if a clipping path includes a rectangle. */
  169. /* The rectangle need not be oriented correctly, i.e. x0 > x1 is OK. */
  170. int
  171. gx_cpath_includes_rectangle(register const gx_clip_path *pcpath,
  172.   fixed x0, fixed y0, fixed x1, fixed y1)
  173. {    return
  174.       (x0 <= x1 ?
  175.         (pcpath->inner_box.p.x <= x0 && x1 <= pcpath->inner_box.q.x) :
  176.         (pcpath->inner_box.p.x <= x1 && x0 <= pcpath->inner_box.q.x)) &&
  177.       (y0 <= y1 ?
  178.         (pcpath->inner_box.p.y <= y0 && y1 <= pcpath->inner_box.q.y) :
  179.         (pcpath->inner_box.p.y <= y1 && y0 <= pcpath->inner_box.q.y));
  180. }
  181.  
  182. /* Set the current outsideness of a clipping path. */
  183. int
  184. gx_cpath_set_outside(gx_clip_path *pcpath, bool outside)
  185. {    if ( outside != pcpath->list.outside )
  186.       { pcpath->id = gs_next_ids(1);    /* path changed => change id */
  187.         pcpath->list.outside = outside;
  188.       }
  189.     return 0;
  190. }
  191.  
  192. /* Return the current outsideness of a clipping path. */
  193. int
  194. gx_cpath_is_outside(const gx_clip_path *pcpath)
  195. {    return pcpath->list.outside;
  196. }
  197.  
  198. /* Release a clipping path. */
  199. void
  200. gx_cpath_release(gx_clip_path *pcpath)
  201. {    if ( !pcpath->shares_list )
  202.         gx_clip_list_free(&pcpath->list, pcpath->path.memory);
  203.     gx_path_release(&pcpath->path);
  204. }
  205.  
  206. /* Share a clipping path. */
  207. void
  208. gx_cpath_share(gx_clip_path *pcpath)
  209. {    gx_path_share(&pcpath->path);
  210.     pcpath->shares_list = 1;
  211. }
  212.  
  213. /* Set the outer clipping box to the path bounding box, */
  214. /* expanded to pixel boundaries. */
  215. void
  216. gx_cpath_set_outer_box(gx_clip_path *pcpath)
  217. {    pcpath->outer_box.p.x = fixed_floor(pcpath->path.bbox.p.x);
  218.     pcpath->outer_box.p.y = fixed_floor(pcpath->path.bbox.p.y);
  219.     pcpath->outer_box.q.x = fixed_ceiling(pcpath->path.bbox.q.x);
  220.     pcpath->outer_box.q.y = fixed_ceiling(pcpath->path.bbox.q.y);
  221. }
  222.  
  223. /* ------ Clipping path setting ------ */
  224.  
  225. /* Initialize a clipping path. */
  226. int
  227. gx_cpath_init(gx_clip_path *pcpath, gs_memory_t *mem)
  228. {    static /*const*/ gs_fixed_rect null_rect = { { 0, 0 }, { 0, 0 } };
  229.     return gx_cpath_from_rectangle(pcpath, &null_rect, mem); /* does a gx_path_init */
  230. }
  231.  
  232. /* Create a rectangular clipping path. */
  233. /* The supplied rectangle may not be oriented correctly, */
  234. /* but it will be oriented correctly upon return. */
  235. int
  236. gx_cpath_from_rectangle(gx_clip_path *pcpath, gs_fixed_rect *pbox,
  237.   gs_memory_t *mem)
  238. {    gx_clip_list_from_rectangle(&pcpath->list, pbox);
  239.     pcpath->inner_box = *pbox;
  240.     pcpath->segments_valid = 0;
  241.     pcpath->shares_list = 0;
  242.     gx_path_init(&pcpath->path, mem);
  243.     pcpath->path.bbox = *pbox;
  244.     gx_cpath_set_outer_box(pcpath);
  245.     pcpath->id = gs_next_ids(1);    /* path changed => change id */
  246.     return 0;
  247. }
  248.  
  249. /* Intersect a new clipping path with an old one. */
  250. /* Note that it may overwrite its path argument; return 1 in this case, */
  251. /* otherwise 0 for success, <0 for failure as usual. */
  252. int
  253. gx_cpath_intersect(gs_state *pgs, gx_clip_path *pcpath, gx_path *ppath,
  254.   int rule)
  255. {    gs_fixed_rect old_box, new_box;
  256.     int code;
  257.  
  258.     if ( gx_cpath_inner_box(pcpath, &old_box) &&
  259.          ((code = gx_path_is_rectangle(ppath, &new_box)) ||
  260.           gx_path_is_void(ppath))
  261.        )
  262.        {    bool changed = false;
  263.         bool outside = pcpath->list.outside;
  264.  
  265.         if ( !code )
  266.           { /* The new path is void. */
  267.             if ( gx_path_current_point(ppath, &new_box.p) < 0 )
  268.               { /* Use the user space origin (arbitrarily). */
  269.             gs_point origin;
  270.  
  271.             gs_transform(pgs, 0.0, 0.0, &origin);
  272.             new_box.p.x = float2fixed(origin.x);
  273.             new_box.p.y = float2fixed(origin.y);
  274.                 gx_path_add_point(ppath, new_box.p.x, new_box.p.y);
  275.               }
  276.             new_box.q = new_box.p;
  277.           }
  278.         else
  279.           { /* Intersect the two rectangles if necessary. */
  280.             if ( old_box.p.x > new_box.p.x )
  281.               new_box.p.x = old_box.p.x, changed = true;
  282.             if ( old_box.p.y > new_box.p.y )
  283.               new_box.p.y = old_box.p.y, changed = true;
  284.             if ( old_box.q.x < new_box.q.x )
  285.               new_box.q.x = old_box.q.x, changed = true;
  286.             if ( old_box.q.y < new_box.q.y )
  287.               new_box.q.y = old_box.q.y, changed = true;
  288.             /* Check for a degenerate rectangle. */
  289.             if ( new_box.q.x < new_box.p.x )
  290.               new_box.q.x = new_box.p.x;
  291.             if ( new_box.q.y < new_box.p.y )
  292.               new_box.q.y = new_box.p.y;
  293.             if ( changed )
  294.               { /* Store the new rectangle back into the new path. */
  295.             register segment *pseg =
  296.               (segment *)ppath->first_subpath;
  297. #define set_pt(pqx,pqy)\
  298.   pseg->pt.x = new_box.pqx.x, pseg->pt.y = new_box.pqy.y
  299.             set_pt(p, p); pseg = pseg->next;
  300.             set_pt(q, p); pseg = pseg->next;
  301.             set_pt(q, q); pseg = pseg->next;
  302.             set_pt(p, q); pseg = pseg->next;
  303.             if ( pseg != 0 ) /* might be an open rectangle */
  304.               set_pt(p, p);
  305. #undef set_pt
  306.               }
  307.           }
  308.         ppath->bbox = new_box;
  309.         gx_cpath_release(pcpath);
  310.         gx_clip_list_from_rectangle(&pcpath->list, &new_box);
  311.         pcpath->list.outside = outside;
  312.         pcpath->inner_box = new_box;
  313.         pcpath->path = *ppath;
  314.         gx_cpath_set_outer_box(pcpath);
  315.         pcpath->segments_valid = 1;
  316.         pcpath->shares_list = 0;
  317.         code = 1;
  318.         pcpath->id = gs_next_ids(1);    /* path changed => change id */
  319.        }
  320.     else
  321.        {    /* Not a rectangle.  Intersect the slow way. */
  322.         code = gx_cpath_intersect_slow(pgs, pcpath, ppath, rule);
  323.        }
  324.     return code;
  325. }
  326.  
  327. /* Scale a clipping path by a power of 2. */
  328. int
  329. gx_cpath_scale_exp2(gx_clip_path *pcpath, int log2_scale_x, int log2_scale_y)
  330. {    int code =
  331.       gx_path_scale_exp2(&pcpath->path, log2_scale_x, log2_scale_y);
  332.     gx_clip_rect *pr;
  333.     if ( code < 0 )
  334.       return code;
  335.     /* Scale the fixed entries. */
  336.     gx_rect_scale_exp2(&pcpath->inner_box, log2_scale_x, log2_scale_y);
  337.     gx_rect_scale_exp2(&pcpath->outer_box, log2_scale_x, log2_scale_y);
  338.     /* Scale the clipping list. */
  339.     pr = pcpath->list.head;
  340.     if ( pr == 0 )
  341.       pr = &pcpath->list.single;
  342.     for ( ; pr != 0; pr = pr->next )
  343.       if ( pr != pcpath->list.head && pr != pcpath->list.tail )
  344.         {
  345. #define scale_v(v, s)\
  346.   if ( pr->v != min_int && pr->v != max_int )\
  347.     pr->v = (s >= 0 ? pr->v << s : pr->v >> -s)
  348.         scale_v(xmin, log2_scale_x);
  349.         scale_v(xmax, log2_scale_x);
  350.         scale_v(ymin, log2_scale_y);
  351.         scale_v(ymax, log2_scale_y);
  352. #undef scale_v
  353.         }
  354.     pcpath->id = gs_next_ids(1);    /* path changed => change id */
  355.     return 0;
  356. }
  357.  
  358. /* ------ Clipping list routines ------ */
  359.  
  360. /* Initialize a clip list. */
  361. void
  362. gx_clip_list_init(gx_clip_list *clp)
  363. {    *clp = clip_list_empty;
  364. }
  365.  
  366. /* Initialize a clip list to a rectangle. */
  367. /* The supplied rectangle may not be oriented correctly, */
  368. /* but it will be oriented correctly upon return. */
  369. private void
  370. gx_clip_list_from_rectangle(register gx_clip_list *clp,
  371.   register gs_fixed_rect *rp)
  372. {    gx_clip_list_init(clp);
  373.     if ( rp->p.x > rp->q.x )
  374.       { fixed t = rp->p.x; rp->p.x = rp->q.x; rp->q.x = t; }
  375.     if ( rp->p.y > rp->q.y )
  376.       { fixed t = rp->p.y; rp->p.y = rp->q.y; rp->q.y = t; }
  377.     clp->single.xmin = fixed2int_var(rp->p.x);
  378.     clp->single.ymin = fixed2int_var(rp->p.y);
  379.     clp->single.xmax = fixed2int_var_ceiling(rp->q.x);
  380.     clp->single.ymax = fixed2int_var_ceiling(rp->q.y);
  381.     clp->count = 1;
  382.     clp->outside = false;
  383. }
  384.  
  385. /* Add a clip list to a path. */
  386. /* In general, this produces a path made up of zillions of tiny lines. */
  387. private int
  388. gx_clip_list_add_to_path(gx_clip_list *clp, gx_path *ppath)
  389. {    gx_clip_rect *rp;
  390.     int code = -1;
  391.     gx_clip_rect *head = (clp->count <= 1 ? &clp->single : clp->head);
  392.     gx_clip_rect *visit;
  393.     gx_clip_rect *look;
  394.     enum { visit_left = 1, visit_right = 2 } first_visit;
  395.  
  396.     for ( rp = head; rp != 0; rp = rp->next )
  397.       if ( rp->xmin < rp->xmax && rp->ymin < rp->ymax )
  398.         rp->to_visit = visit_left | visit_right;
  399.     for ( visit = head; visit != 0; visit = visit->next )
  400.       { if ( !visit->to_visit )
  401.           continue;
  402.         rp = visit;
  403.         if ( visit->to_visit & visit_left )
  404.           { code = gx_path_add_point(ppath, int2fixed(visit->xmin),
  405.                      int2fixed(visit->ymax));
  406.             if ( code < 0 )
  407.           return code;
  408.         first_visit = visit_left;
  409.         goto left;
  410.           }
  411.         else
  412.           { code = gx_path_add_point(ppath, int2fixed(visit->xmax),
  413.                      int2fixed(visit->ymin));
  414.             if ( code < 0 )
  415.           return code;
  416.         first_visit = visit_right;
  417.         goto right;
  418.           }
  419. #define trace_line(px, py)\
  420.   code = gx_path_add_line(ppath, int2fixed(px), int2fixed(py));\
  421.   if ( code < 0 ) return code
  422. left:        /* Trace upward along a left edge. */
  423.         /* We're at the upper left corner of rp. */
  424.         rp->to_visit &= ~visit_left;
  425.         /* Look for an adjacent rectangle above rp. */
  426.         for ( look = rp;
  427.           (look = look->next) != 0 &&
  428.             (look->ymin == rp->ymin ||
  429.              (look->ymin == rp->ymax && look->xmax <= rp->xmin));
  430.         )
  431.           ;
  432.         /* Now we know look->ymin >= rp->ymax. */
  433.         if ( look == 0 || look->ymin > rp->ymax || look->xmin >= rp->xmax )
  434.           { /* No adjacent rectangle, switch directions. */
  435.         trace_line(rp->xmax, rp->ymax);
  436.         if ( rp == visit && first_visit == visit_right )
  437.           goto close;
  438.         goto right1;
  439.           }
  440.         /* We found an adjacent rectangle. */
  441.         /* See if it also adjoins a rectangle to the left of rp. */
  442.         { gx_clip_rect *prev = rp->prev;
  443.           if ( prev->ymax == rp->ymax && look->xmin < prev->xmax )
  444.         { /* There's an adjoining rectangle as well. */
  445.           /* Switch directions. */
  446.           trace_line(prev->xmax, rp->ymax);
  447.           rp = prev;
  448.           if ( rp == visit && first_visit == visit_right )
  449.             goto close;
  450.           goto right1;
  451.         }
  452.         }
  453.         trace_line(look->xmin, look->ymin);
  454.         rp = look;
  455.         if ( rp == visit && first_visit == visit_left )
  456.           goto close;
  457. left1:        trace_line(rp->xmin, rp->ymax);
  458.         goto left;
  459. right:        /* Trace downward along a right edge. */
  460.         /* We're at the lower right corner of rp. */
  461.         rp->to_visit &= ~visit_right;
  462.         /* Look for an adjacent rectangle below rp. */
  463.         for ( look = rp;
  464.           (look = look->prev) != 0 &&
  465.             (look->ymax == rp->ymax ||
  466.              (look->ymax == rp->ymin && look->xmin >= rp->xmax));
  467.         )
  468.           ;
  469.         /* Now we know look->ymax <= rp->ymin. */
  470.         if ( look == 0 || look->ymax < rp->ymin || look->xmax <= rp->xmin )
  471.           { /* No adjacent rectangle, switch directions. */
  472.         trace_line(rp->xmin, rp->ymin);
  473.         if ( rp == visit && first_visit == visit_left )
  474.           goto close;
  475.         goto left1;
  476.           }
  477.         /* We found an adjacent rectangle. */
  478.         /* See if it also adjoins a rectangle to the right of rp. */
  479.         { gx_clip_rect *next = rp->next;
  480.           if ( next->ymin == rp->ymin && look->xmax > next->xmin )
  481.         { /* There's an adjoining rectangle as well. */
  482.           /* Switch directions. */
  483.           trace_line(next->xmin, rp->ymin);
  484.           rp = next;
  485.           if ( rp == visit && first_visit == visit_left )
  486.             goto close;
  487.           goto left1;
  488.         }
  489.         }
  490.         trace_line(look->xmax, look->ymax);
  491.         rp = look;
  492.         if ( rp == visit && first_visit == visit_right )
  493.           goto close;
  494. right1:        trace_line(rp->xmax, rp->ymin);
  495.         goto right;
  496. close:        /* We've gone all the way around an edge. */
  497.         code = gx_path_close_subpath(ppath);
  498.         if ( code < 0 )
  499.           return code;
  500.       }
  501. #undef trace_line
  502.     if ( code < 0 )
  503.     {    /* We didn't have any rectangles. */
  504.         code = gx_path_add_point(ppath, fixed_0, fixed_0);
  505.     }
  506.     return code;
  507. }
  508.  
  509. /* Free a clip list. */
  510. void
  511. gx_clip_list_free(gx_clip_list *clp, gs_memory_t *mem)
  512. {    gx_clip_rect *rp = clp->tail;
  513.     while ( rp != 0 )
  514.     {    gx_clip_rect *prev = rp->prev;
  515.         gs_free_object(mem, rp, "gx_clip_list_free");
  516.         rp = prev;
  517.     }
  518.     gx_clip_list_init(clp);
  519. }
  520.  
  521. /* ------ Rectangle list clipper ------ */
  522.  
  523. /* Device for clipping with a region. */
  524. /* We forward non-drawing operations, but we must be sure to intercept */
  525. /* all drawing operations. */
  526. private dev_proc_open_device(clip_open);
  527. private dev_proc_fill_rectangle(clip_fill_rectangle);
  528. private dev_proc_copy_mono(clip_copy_mono);
  529. private dev_proc_copy_color(clip_copy_color);
  530. private dev_proc_get_bits(clip_get_bits);
  531. private dev_proc_copy_alpha(clip_copy_alpha);
  532. private dev_proc_fill_mask(clip_fill_mask);
  533. private dev_proc_strip_tile_rectangle(clip_strip_tile_rectangle);
  534. private dev_proc_strip_copy_rop(clip_strip_copy_rop);
  535. private dev_proc_get_clipping_box(clip_get_clipping_box);
  536.  
  537. /* The device descriptor. */
  538. private const gx_device_clip gs_clip_device =
  539. {    std_device_std_body(gx_device_clip, 0, "clipper",
  540.       0, 0, 1, 1),
  541.     {    clip_open,
  542.         gx_forward_get_initial_matrix,
  543.         gx_default_sync_output,
  544.         gx_default_output_page,
  545.         gx_default_close_device,
  546.         gx_forward_map_rgb_color,
  547.         gx_forward_map_color_rgb,
  548.         clip_fill_rectangle,
  549.         gx_default_tile_rectangle,
  550.         clip_copy_mono,
  551.         clip_copy_color,
  552.         gx_default_draw_line,
  553.         clip_get_bits,
  554.         gx_forward_get_params,
  555.         gx_forward_put_params,
  556.         gx_forward_map_cmyk_color,
  557.         gx_forward_get_xfont_procs,
  558.         gx_forward_get_xfont_device,
  559.         gx_forward_map_rgb_alpha_color,
  560.         gx_forward_get_page_device,
  561.         gx_forward_get_alpha_bits,
  562.         clip_copy_alpha,
  563.         gx_forward_get_band,
  564.         gx_default_copy_rop,
  565.         gx_default_fill_path,
  566.         gx_default_stroke_path,
  567.         clip_fill_mask,
  568.         gx_default_fill_trapezoid,
  569.         gx_default_fill_parallelogram,
  570.         gx_default_fill_triangle,
  571.         gx_default_draw_thin_line,
  572.         gx_default_begin_image,
  573.         gx_default_image_data,
  574.         gx_default_end_image,
  575.         clip_strip_tile_rectangle,
  576.         clip_strip_copy_rop,
  577.         clip_get_clipping_box
  578.     }
  579. };
  580. #define rdev ((gx_device_clip *)dev)
  581.  
  582. /* Make a clipping device. */
  583. void
  584. gx_make_clip_translate_device(gx_device_clip *dev, void *container,
  585.   const gx_clip_list *list, int tx, int ty)
  586. {    *dev = gs_clip_device;
  587.     dev->list = *list;
  588.     dev->translation.x = tx;
  589.     dev->translation.y = ty;
  590. }
  591. void
  592. gx_make_clip_path_device(gx_device_clip *dev, const gx_clip_path *pcpath)
  593. {    gx_make_clip_device(dev, NULL, &pcpath->list);
  594. }
  595.  
  596. /* Declare and initialize the cursor variables. */
  597. #ifdef DEBUG
  598. private ulong clip_loops, clip_in, clip_down, clip_up, clip_x, clip_no_x;
  599. private uint clip_interval = 10000;
  600. # define inc(v) v++
  601. # define print_clip()\
  602.     if ( clip_loops % clip_interval == 0 )\
  603.       if_debug10('q', "[q]rect=(%d,%d),(%d,%d)\n     loops=%ld in=%ld down=%ld up=%ld x=%ld no_x=%ld\n",\
  604.          x, y, x + w, y + h,\
  605.          clip_loops, clip_in, clip_down, clip_up, clip_x, clip_no_x)
  606. #else
  607. # define inc(v) discard(0)
  608. # define print_clip() DO_NOTHING
  609. #endif
  610. #define DECLARE_CLIP\
  611.   register gx_clip_rect *rptr = rdev->current;\
  612.   gx_device *tdev = rdev->target;\
  613.   bool outside = rdev->list.outside;
  614. /* Translate the supplied coordinates. */
  615. #define TRANSLATE_CLIP\
  616.   x += rdev->translation.x;\
  617.   y += rdev->translation.y;
  618. /* Check whether the rectangle x,y,w,h falls within the current entry. */
  619. #define xywh_is_in_ryptr()\
  620.   (!outside &&\
  621.    y >= rptr->ymin && y + h <= rptr->ymax &&\
  622.    x >= rptr->xmin && x + w <= rptr->xmax)
  623. #ifdef DEBUG
  624. #  define xywh_in_ryptr() (xywh_is_in_ryptr() ? (inc(clip_in), 1) : 0)
  625. #else
  626. #  define xywh_in_ryptr() xywh_is_in_ryptr()
  627. #endif
  628. /*
  629.  * Warp the cursor forward or backward to the first rectangle row that
  630.  * could include a given y value.  Assumes rptr is set, and updates it.
  631.  * Specifically, after warp_cursor, either rptr == 0 (if the y value is
  632.  * greater than all y values in the list), or y < rptr->ymax and either
  633.  * rptr->prev == 0 or y >= rptr->prev->ymax.  Note that y <= rptr->ymin
  634.  * is possible.
  635.  *
  636.  * In the first case below, the while loop is safe because if there is
  637.  * more than one rectangle, there is a 'stopper' at the end of the list.
  638.  */
  639. #define warp_cursor(y)\
  640.   if ( (y) >= rptr->ymax )\
  641.    { if ( (rptr = rptr->next) != 0 )\
  642.        while ( inc(clip_up), (y) >= rptr->ymax ) rptr = rptr->next;\
  643.    }\
  644.   else while ( rptr->prev != 0 && (y) < rptr->prev->ymax )\
  645.    { inc(clip_down); rptr = rptr->prev; }
  646. /*
  647.  * Enumerate the rectangles of the x,w,y,h argument that fall within
  648.  * the clipping region.  Usage:
  649.  *    DO_CLIP(adjust for yc > yp if necessary,
  650.  *        process(xc, yc, xec, yec) [must be an expression])
  651.  *
  652.  * Note that we look ahead to detect unclipped vertical strips.
  653.  * This is really only valuable for 90 degree rotated images or
  654.  * (nearly-)vertical lines with convex clipping regions; if we ever
  655.  * change images to use source buffering and destination-oriented
  656.  * enumeration, we could probably take out the code here with no
  657.  * adverse effects.
  658.  */
  659. #ifdef CHECK_VERTICAL_CLIPPING
  660. #  define LOOK_AHEAD\
  661.                 if ( xec - xc == w )    /* full width */\
  662.                   { /* Look ahead for a vertical swath. */\
  663.                     while ( (nptr = rptr->next) != 0 &&\
  664.                         nptr->ymin == yec &&\
  665.                         nptr->ymax <= ye &&\
  666.                         nptr->xmin <= x &&\
  667.                         nptr->xmax >= xe\
  668.                       )\
  669.                       yec = nptr->ymax, rptr = nptr;\
  670.                   }\
  671.                 else\
  672.                   nptr = rptr->next
  673. #else
  674. #  define LOOK_AHEAD\
  675.                   nptr = rptr->next
  676. #endif
  677. #define DO_CLIP(adjust_for_y, process_rectangle)\
  678.     if ( w <= 0 || h <= 0 ) return 0;\
  679.     inc(clip_loops);\
  680.     print_clip();\
  681.    {    const int xe = x + w, ye = y + h;\
  682.     int xc, xec, yc, yec, yp, yep;\
  683.     int code;\
  684. \
  685.     warp_cursor(y);\
  686.     if ( rptr == 0 || (yc = rptr->ymin) >= ye )\
  687.       { if ( rdev->list.count > 1 )\
  688.           rdev->current =\
  689.         (rptr != 0 ? rptr :\
  690.          y >= rdev->current->ymax ? rdev->list.tail :\
  691.          rdev->list.head);\
  692.         return (outside ? (xc = x, xec = xe, yc = y, yec = ye,\
  693.                    process_rectangle) : 0);\
  694.       }\
  695.     rdev->current = rptr;\
  696.     if ( yc < y ) yc = y;\
  697.     yp = y;\
  698.     if ( outside )\
  699.       { for ( yep = y; ; )\
  700.           { const int ymax = rptr->ymax;\
  701. \
  702.         xc = x;\
  703.         if ( yc > yep )\
  704.           { yec = yc, yc = yep;\
  705.             adjust_for_y;\
  706.             xec = xe;\
  707.             code = process_rectangle;\
  708.             if ( code < 0 ) return code;\
  709.             yp = yep;\
  710.             yc = yec;\
  711.             adjust_for_y;\
  712.           }\
  713.         yec = min(ymax, ye);\
  714.         do \
  715.            {    xec = rptr->xmin;\
  716.             if ( xec > xc )\
  717.                {    if ( xec > xe ) xec = xe;\
  718.                 code = process_rectangle;\
  719.                 if ( code < 0 ) return code;\
  720.                 xc = rptr->xmax;\
  721.                 if ( xc >= xe ) xc = max_int;\
  722.                }\
  723.             else\
  724.               { xec = rptr->xmax;\
  725.                 if ( xec > xc ) xc = xec;\
  726.               }\
  727.            }\
  728.         while ( (rptr = rptr->next) != 0 && rptr->ymax == ymax );\
  729.         if ( xc < xe )\
  730.           { xec = xe;\
  731.             code = process_rectangle;\
  732.             if ( code < 0 ) return code;\
  733.           }\
  734.         yp = yc;\
  735.         yep = yec;\
  736.         if ( rptr == 0 || (yc = rptr->ymin) >= ye ) break;\
  737.           }\
  738.         if ( yep < ye )\
  739.           { xc = x, xec = xe, yc = yep, yec = ye;\
  740.         code = process_rectangle;\
  741.         if ( code < 0 ) return code;\
  742.           }\
  743.       }\
  744.     else \
  745.       for ( ; ; )\
  746.         {    const int ymax = rptr->ymax;\
  747.         gx_clip_rect *nptr;\
  748. \
  749.         yec = min(ymax, ye);\
  750.         if ( yc > yp ) adjust_for_y;\
  751.         if_debug2('Q', "[Q]yc=%d yec=%d\n", yc, yec);\
  752.         do \
  753.            {    xc = rptr->xmin;\
  754.             xec = rptr->xmax;\
  755.             if ( xc < x ) xc = x;\
  756.             if ( xec > xe ) xec = xe;\
  757.             if ( xec > xc )\
  758.                {    clip_rect_print('Q', "match", rptr);\
  759.                 if_debug2('Q', "[Q]xc=%d xec=%d\n", xc, xec);\
  760.                 inc(clip_x);\
  761.                 LOOK_AHEAD;\
  762.                 code = process_rectangle;\
  763.                 if ( code < 0 ) return code;\
  764.                }\
  765.             else\
  766.               { inc(clip_no_x);\
  767.                 nptr = rptr->next;\
  768.               }\
  769.            }\
  770.         while ( (rptr = nptr) != 0 && rptr->ymax == ymax );\
  771.         if ( rptr == 0 || (yec = rptr->ymin) >= ye ) break;\
  772.         yp = yc;\
  773.         yc = yec;\
  774.         }\
  775.    }
  776.  
  777. /* Open a clipping device */
  778. private int
  779. clip_open(register gx_device *dev)
  780. {    gx_device *tdev = rdev->target;
  781.     /* Initialize the cursor. */
  782.     rdev->current =
  783.       (rdev->list.head == 0 ? &rdev->list.single : rdev->list.head);
  784.     rdev->color_info = tdev->color_info;
  785.     rdev->width = tdev->width;
  786.     rdev->height = tdev->height;
  787.     return 0;
  788. }
  789.  
  790. /* Fill a rectangle */
  791. private int
  792. clip_fill_rectangle(gx_device *dev, int x, int y, int w, int h,
  793.   gx_color_index color)
  794. {    DECLARE_CLIP
  795.     dev_proc_fill_rectangle((*fill)) = dev_proc(tdev, fill_rectangle);
  796.  
  797.     TRANSLATE_CLIP
  798.     if ( xywh_in_ryptr() )
  799.       return (*fill)(tdev, x, y, w, h, color);
  800.     DO_CLIP(DO_NOTHING,
  801.         (*fill)(tdev, xc, yc, xec - xc, yec - yc, color))
  802.     return 0;
  803. }
  804.  
  805. /* Copy a monochrome rectangle */
  806. private int
  807. clip_copy_mono(gx_device *dev,
  808.   const byte *data, int sourcex, int raster, gx_bitmap_id id,
  809.   int x, int y, int w, int h,
  810.   gx_color_index color0, gx_color_index color1)
  811. {    DECLARE_CLIP
  812.     dev_proc_copy_mono((*copy)) = dev_proc(tdev, copy_mono);
  813.  
  814.     TRANSLATE_CLIP
  815.     if ( xywh_in_ryptr() )
  816.       return (*copy)(tdev, data, sourcex, raster, id, x, y, w, h, color0, color1);
  817.     DO_CLIP(data += (yc - yp) * raster,
  818.         (*copy)(tdev, data, sourcex + xc - x, raster, gx_no_bitmap_id,
  819.             xc, yc, xec - xc, yec - yc, color0, color1))
  820.     return 0;
  821. }
  822.  
  823. /* Copy a color rectangle */
  824. private int
  825. clip_copy_color(gx_device *dev,
  826.   const byte *data, int sourcex, int raster, gx_bitmap_id id,
  827.   int x, int y, int w, int h)
  828. {    DECLARE_CLIP
  829.     dev_proc_copy_color((*copy)) = dev_proc(tdev, copy_color);
  830.  
  831.     TRANSLATE_CLIP
  832.     if ( xywh_in_ryptr() )
  833.       return (*copy)(tdev, data, sourcex, raster, id, x, y, w, h);
  834.     DO_CLIP(data += (yc - yp) * raster,
  835.         (*copy)(tdev, data, sourcex + xc - x, raster, gx_no_bitmap_id,
  836.             xc, yc, xec - xc, yec - yc))
  837.     return 0;
  838. }
  839.  
  840. /* Copy a rectangle with alpha */
  841. private int
  842. clip_copy_alpha(gx_device *dev,
  843.   const byte *data, int sourcex, int raster, gx_bitmap_id id,
  844.   int x, int y, int w, int h,
  845.   gx_color_index color, int depth)
  846. {    DECLARE_CLIP
  847.     dev_proc_copy_alpha((*copy)) = dev_proc(tdev, copy_alpha);
  848.  
  849.     TRANSLATE_CLIP
  850.     if ( xywh_in_ryptr() )
  851.       return (*copy)(tdev, data, sourcex, raster, id, x, y, w, h, color, depth);
  852.     DO_CLIP(data += (yc - yp) * raster,
  853.         (*copy)(tdev, data, sourcex + xc - x, raster, gx_no_bitmap_id,
  854.             xc, yc, xec - xc, yec - yc, color, depth))
  855.     return 0;
  856. }
  857.  
  858. /* Fill a region defined by a mask. */
  859. private int
  860. clip_fill_mask(gx_device *dev,
  861.   const byte *data, int sourcex, int raster, gx_bitmap_id id,
  862.   int x, int y, int w, int h,
  863.   const gx_drawing_color *pdcolor, int depth,
  864.   gs_logical_operation_t lop, const gx_clip_path *pcpath)
  865. {    DECLARE_CLIP
  866.     dev_proc_fill_mask((*fill)) = dev_proc(tdev, fill_mask);
  867.  
  868.     if ( pcpath != 0 )
  869.       return gx_default_fill_mask(dev, data, sourcex, raster, id,
  870.                       x, y, w, h, pdcolor, depth, lop,
  871.                       pcpath);
  872.     TRANSLATE_CLIP
  873.     if ( xywh_in_ryptr() )
  874.       return (*fill)(tdev, data, sourcex, raster, id, x, y, w, h,
  875.              pdcolor, depth, lop, NULL);
  876.     DO_CLIP(data += (yc - yp) * raster,
  877.         (*fill)(tdev, data, sourcex + xc - x, raster, gx_no_bitmap_id,
  878.             xc, yc, xec - xc, yec - yc, pdcolor, depth, lop,
  879.             NULL))
  880.     return 0;
  881. }
  882.  
  883. /* Get bits back from the device. */
  884. private int
  885. clip_get_bits(gx_device *dev, int y, byte *data, byte **actual_data)
  886. {    gx_device *tdev = rdev->target;
  887.     return (*dev_proc(tdev, get_bits))(tdev, y - rdev->translation.y,
  888.                        data, actual_data);
  889. }
  890.  
  891. /* Strip-tile a rectangle. */
  892. private int
  893. clip_strip_tile_rectangle(gx_device *dev, const gx_strip_bitmap *tiles,
  894.   int x, int y, int w, int h,
  895.   gx_color_index color0, gx_color_index color1, int phase_x, int phase_y)
  896. {    DECLARE_CLIP
  897.     dev_proc_strip_tile_rectangle((*fill)) =
  898.       dev_proc(tdev, strip_tile_rectangle);
  899.  
  900.     TRANSLATE_CLIP
  901.     if ( xywh_in_ryptr() )
  902.       return (*fill)(tdev, tiles, x, y, w, h, color0, color1, phase_x, phase_y);
  903.     DO_CLIP(DO_NOTHING,
  904.         (*fill)(tdev, tiles, xc, yc, xec - xc, yec - yc,
  905.             color0, color1, phase_x, phase_y))
  906.     return 0;
  907. }
  908.  
  909. /* Copy a rectangle with RasterOp and strip texture. */
  910. private int
  911. clip_strip_copy_rop(gx_device *dev,
  912.   const byte *sdata, int sourcex, uint raster, gx_bitmap_id id,
  913.   const gx_color_index *scolors,
  914.   const gx_strip_bitmap *textures, const gx_color_index *tcolors,
  915.   int x, int y, int w, int h,
  916.   int phase_x, int phase_y, gs_logical_operation_t lop)
  917. {    DECLARE_CLIP
  918.     dev_proc_strip_copy_rop((*copy)) = dev_proc(tdev, strip_copy_rop);
  919.  
  920.     TRANSLATE_CLIP
  921.     if ( xywh_in_ryptr() )
  922.       return (*copy)(tdev, sdata, sourcex, raster, id, scolors,
  923.              textures, tcolors, x, y, w, h,
  924.              phase_x, phase_y, lop);
  925.     DO_CLIP(sdata += (yc - yp) * raster,
  926.         (*copy)(tdev, sdata, sourcex + xc - x, raster,
  927.             gx_no_bitmap_id, scolors, textures, tcolors,
  928.             xc, yc, xec - xc, yec - yc,
  929.             phase_x, phase_y, lop))
  930.     return 0;
  931. }
  932.  
  933. /* Get the (outer) clipping box, in client coordinates. */
  934. private void
  935. clip_get_clipping_box(gx_device *dev, gs_fixed_rect *pbox)
  936. {    gx_device *tdev = rdev->target;
  937.     gs_fixed_rect tbox, cbox;
  938.     fixed tx = int2fixed(rdev->translation.x),
  939.       ty = int2fixed(rdev->translation.y);
  940.  
  941.     (*dev_proc(tdev, get_clipping_box))(tdev, &tbox);
  942.     /*
  943.      * To get an accurate clipping box quickly in all cases, we should
  944.      * save the outer box from the clipping path.  However,
  945.      * this is not currently (or even always guaranteed to be)
  946.      * available.  Instead, we compromise: if there is more than one
  947.      * rectangle in the list, we return accurate Y values (which are
  948.      * easy to obtain, because the list is Y-sorted) but copy the
  949.      * X values from the target.
  950.      */
  951.     if ( rdev->list.outside || rdev->list.count == 0 )
  952.       { cbox = tbox;
  953.       }
  954.     else if ( rdev->list.count == 1 )
  955.       { cbox.p.x = int2fixed(rdev->list.single.xmin);
  956.         cbox.p.y = int2fixed(rdev->list.single.ymin);
  957.         cbox.q.x = int2fixed(rdev->list.single.xmax);
  958.         cbox.q.y = int2fixed(rdev->list.single.ymax);
  959.       }
  960.     else
  961.       { /* The head and tail elements are dummies.... */
  962.         cbox.p.x = tbox.p.x;
  963.         cbox.p.y = int2fixed(rdev->list.head->next->ymin);
  964.         cbox.q.x = tbox.q.x;
  965.         cbox.q.y = int2fixed(rdev->list.tail->prev->ymax);
  966.       }
  967.     rect_intersect(tbox, cbox);
  968.     if ( tbox.p.x != min_fixed )
  969.       tbox.p.x -= tx;
  970.     if ( tbox.p.y != min_fixed )
  971.       tbox.p.y -= ty;
  972.     if ( tbox.q.x != max_fixed )
  973.       tbox.q.x -= tx;
  974.     if ( tbox.q.y != max_fixed )
  975.       tbox.q.y -= ty;
  976.     *pbox = tbox;
  977. }
  978.  
  979. /* ------ Debugging printout ------ */
  980.  
  981. #ifdef DEBUG
  982.  
  983. /* Print a clipping path */
  984. void
  985. gx_cpath_print(const gx_clip_path *pcpath)
  986. {    const gx_clip_rect *pr;
  987.     if ( pcpath->segments_valid )
  988.         gx_path_print(&pcpath->path);
  989.     else
  990.         dputs("   (segments not valid)\n");
  991.     dprintf4("   inner_box=(%g,%g),(%g,%g)\n",
  992.          fixed2float(pcpath->inner_box.p.x),
  993.          fixed2float(pcpath->inner_box.p.y),
  994.          fixed2float(pcpath->inner_box.q.x),
  995.          fixed2float(pcpath->inner_box.q.y));
  996.     dprintf5("     outer_box=(%g,%g),(%g,%g) count=%d\n",
  997.          fixed2float(pcpath->outer_box.p.x),
  998.          fixed2float(pcpath->outer_box.p.y),
  999.          fixed2float(pcpath->outer_box.q.x),
  1000.          fixed2float(pcpath->outer_box.q.y),
  1001.          pcpath->list.count);
  1002.     dprintf2("     rule=%d outside=%d\n",
  1003.          pcpath->rule, pcpath->list.outside);
  1004.     switch ( pcpath->list.count )
  1005.     {
  1006.     case 0: pr = 0; break;
  1007.     case 1: pr = &pcpath->list.single; break;
  1008.     default: pr = pcpath->list.head;
  1009.     }
  1010.     for ( ; pr != 0; pr = pr->next )
  1011.       dprintf4("   rect: (%d,%d),(%d,%d)\n",
  1012.            pr->xmin, pr->ymin, pr->xmax, pr->ymax);
  1013. }
  1014.  
  1015. #endif                    /* DEBUG */
  1016.